# !/usr/bin/env python
# A general solution of Eight Queens
# Copyright (C) 2006 Alec Jang <alec.jang@gmail.com>
# 
# This program is free software, you can redistribute it 
# with or without any modifications. It may be interesting or 
# even useful, but without any warranty.
# 
# Description:
#   This is a general method to figuren out all solutions of 
#   eight queens. Certainly, it can also solve any number of queens.
#   Each solution is a list, and each value of the list represents 
#   the column number, at the same time the index of this value
#   represents it's row number. 
#   For instance, list [5,0,4,1,7,2,6,3] means that the first 
#   queen is at (0,5), the second queen is at (1,0), etc.
#   It runs very fast. In my window box, it need within 4 seconds
#   to make all solutions and print them to a file.
#   Only tested at python 2.41
#
# Usage:
#   python queens.py >queens.txt
#
# if you want to get only one solution , or solve other number of 
# queens solution, you can do it like this:
#
# >>>import queens
# >>>q=queens.queens(8)
# >>>queens.print_solution(q.next())
#
# Alec Jang 3/18/2006

import sys

def check_safe(lst):
    """Check if any two elements of lst can form a line, 
    if so, there will be:
    abs(value2-value1)/(index2-index1)==1
    """
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            if abs((lst[j]-lst[i])*1.0/(j-i))==1:
                return False
    return True

def print_solution(lst):
    """Print a solution to stdout
    The argument lst is a nested list
    """
    for i in range(len(lst)):
        stars=['.']*len(lst)
        stars[lst[i]]='Q'
        print stars

def list_mutation(n):
    """Generate all posible layouts of n queens
    """
    if n==0: yield [n]
    else:
        for lst in list_mutation(n-1):
            for i in range(n):
                yield lst[0:n-1-i]+[n-1]+lst[n-1-i:n-1]
                
def queens(n):
    """Find all solutions of queens.
    For each layout generated by list_mutation(n), chech
    if it's safe.
    The augument n is the number of queens. Certainly it 
    can be altered to meet your own needs.
    """
    print "N queens solutions"
    print "By Alec Jang"
    for q in list_mutation(n):
        if check_safe(q):
            yield q

def test():
    """Test 8 queens.
    """
    N=8
    import time
    start=time.time()
    count=0
    for q in queens(N):
        count+=1
        print "solution: ", count, q
        print_solution(q)
    print "Solution count:", count
    print "time: ", time.time()-start

if __name__=="__main__":
    test()
